// 473. 火柴拼正方形
/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */

/* 回溯 */
var makesquare = function (matchsticks) {
	const len = matchsticks.length
	if (len === 1) return false
	const totalLen = matchsticks.reduce((prev, next) => prev + next)
	if (totalLen % 4 !== 0) return false
	matchsticks.sort((a, b) => b - a)
	const edges = new Array(4).fill(0)

	return dfs(0, matchsticks, edges, Math.floor(totalLen / 4))
}
const dfs = (index, matchsticks, edges, len) => {
	if (index === matchsticks.length) return true
	for (let i = 0; i < edges.length; i++) {
		edges[i] += matchsticks[index]
		if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len))
			return true
		edges[i] -= matchsticks[index]
	}
	return false
}
const result = makesquare([10, 6, 5, 5, 5, 3, 3, 3, 2, 2, 2, 2])
console.log('makesquare :>>', result)
